Sets, Logic, Computability

-An Open Logic Text

This textbook is about meta-logic, a discipline where the study is of logic itself. Formal Logic is concerned with studying valid inferences using formal languages and proof systems to express these inferences. Meta-logic investigates the properties of these languages and proof systems.

The goal of the textbook is to give a student who’s had a first class in logic the mathematical background to understand and prove results about formal languages.

It’s organized in 3 parts:

• The first part covers the basics of set theory. Set theory provides one answer to understanding how mathematical objects should be thought of. There’s good reason to become familiar with understanding and constructing mathematical proofs and to become fluent the language which forms the foundation for a lot of other work in math, CS, philosophy, logic, linguistics, etc…
  $\space$

• The second part covers first-order logic, which we will return to the forall x textbook, but this section is worth taking a look at too. The reading here is less forgiving.
  $\space$

• The last part connects logic with computability. As we mentioned, mathematician David Hilbert posed a question with the decision problem, whether there is a mechanical method which would decide, given a sentence of logic, whether it has a proof. We saw that such a method exists for truth functional logic – check the truth table – but it turns out truth tables are not possible for first-order logic, since the number of possible structures is infinite. Eventually Alonzo Church and Alan Turing prove that there is no method that could do this. This means that some problems are impossible – not just impractical – for computers to solve. That’s one of the most important discoveries in computer science.

---

Set theory

Basic definitions for set theory.

Definition 1: A set is a well defined collection of objects, considered as an object itself. The objects making up the set are called elements or members of the set. There is no order to the elements and no multiplicity.

If a is an element of set X, then we write $a \in X$. And if not, we write $a \notin X$.

Sets are conventionally denoted with capital letters.

There is a set with no members, and it’s called the empty set, denoted by $\emptyset$.

There are two ways of describing a set.

• One is by intensional definition, using a rule or semantic description. For example: $S$ is the set containing the siblings of Richard. (Written $S = \{x$ : $x$ is a sibling of Richard$\}$)

• The other is by extension, listing each member of the set. For example: $T = \{1, 2, 3, 4\}$

We often have the choice of specifying a set either intensionally or extensionally. For example: $R = \{x$ : $x$ is one of the first four positive integers$\}$. So $T = R$

Definition 2: If $X$ and $Y$ are sets, then they are identical. (Extensionality) The identity of sets are given by their extensions (the elements they contain). This definition gives us a common proof strategy for proving set identities.

Definition 3: If every element of $X$ is an element of $Y$, then $X$ is a subset of $Y$, symbolically $X \subseteq Y$.

Note that it follows from this definition that every set is a subset of itself.

Also, it’s possible for a set to be an element of another set.

If $X \subseteq Y$ and $Y \not\subseteq X$ then $X \subset Y$. In other words, if every element of $X$ is an element of $Y$, but not every element of $Y$ is an element of $X$, then we say that $X$ is a proper subset of $Y$.

Definition 4: The set consisting of all subsets of $X$ is called the power set of $X$, written $\mathscr{P} (X)$

What are all the possible subsets of $\{a, b, c\}$?

Definition 5: The union of $X$ and $Y$, written $X \cup Y$, is the set of all things which are elements of $X$ or $Y$ or both.

$X \cup Y = \{x$ : $x \in X \lor x \in Y\}$

Venn diagrams can be useful to illustrate union and intersection.

Definition 6: The intersection of $X$ and $Y$, written $X \cap Y$, is the set of all things which are elements of both $X$ and $Y$.

Definition 7: If $Z$ is a set of sets, then $\bigcup Z$ is the set of elements of elements of $Z$.
$\bigcup Z = \{x$ : $x$ belongs to an element of $Z\}$ or
$\bigcup Z = \{x$ : there is a $Y \in Z$ such that $x \in Y\}$

Definition 8: If $Z$ is a set of sets, then $\bigcap Z$ is the set of objects which all elements of $Z$ have in common.
$\bigcap Z = \{x$ : $x$ belongs to every element of $Z\}$ or
$\bigcap Z = \{x$ : for all $Y \in Z$, $x \in Y\}$

Definition 9 The difference $X \setminus Y$ is the set of all elements of $X$ which are not elements of $Y$.
$X \setminus Y = \{x$ : $x\in X$ and $x \notin Y\}$

---

Ordered pairs, Tuples, and Cartesian Products

Sets have no order, but sometimes it is necessary to think of a collection in ordered terms. We use angle brackets to specify ordered pairs, such as $\langle x, y \rangle$. Order matters so $\langle x, y \rangle \neq \langle y, x \rangle$.

Definition 10: Given sets $X$ and $Y$, their Cartesian product $X \times Y = \{\langle x, y \rangle$ : $x \in X$ and $y \in Y\}$.

If $X = \{0, 1\}$ and $Y = \{1, a, b\}$ what is $X \times Y$?

Theorem 1 If $X$ has $n$ elements and $Y$ has $m$ elements, then $X \times Y$ has $n \cdot m$ elements.

Proof p. 10 (SLC)

Russell’s Paradox
In a village, the barber shaves everyone who does not shave themselves, and no one else.

The question that prompts the paradox is this: Does the barber shave himself?

1.3 Informal proof:
If $X$ has $n$ elements then $\mathscr{P}(X)$ has 2^n elements.
Given an element $x$ of $S$, each subset of $S$ either includes $x$ or does not include $x$ (by definition of set), which gives us two possibilities.
The same reasoning holds for any element of $S$.
We can see that this means there are 2 * 2 * … * 2 = 2^|$S$| total possible combinations of elements of $S$.

We’ll come back to mathematical induction.